An exchange is a market mechanism that allows trading between multiple sellers and buyers (collectively called agents) by aggregating their supply and demand to clear the market. It can be advantageous to allow several heterogeneous items to be traded in the same exchange simultaneously (rather than in separate exchanges, simultaneously or sequentially) if there is synergy or substitutability between items. Such exchanges are termed combinatorial because agents can express their preferences across combinations (bundles) of items. Note that auctions are a special case of exchanges where there is only one seller (forward auction) or one buyer (reverse auction).
While a great number of possible exchange schemes could be constructed (with many rounds and complex rules), we may focus on a single-round, or “one-shot” exchange, by virtue of the Revelation Principle, as derived by Roger B. Myerson, Optimal auction design, Mathematics of Operations Research, Vol. 6 No. 1 February 1981, the disclosures of which are incorporated by reference herein in their entirety. While the exchange is open, agents may submit bids (requests to buy items for no more than the bid price) and asks (offers to sell items for at least the ask price). After the exchange closes the exchange engine clears the market by computing a matching of asks to bids and determining the payments to be made or received by the agents. Ideally, the trades and the payments should be determined in such a way that the following economic properties are induced:    Allocative Efficiency (AE): The set of trades are determined so as to maximize the total valuation over all agents participating in the exchange.    Budget-Balance (BB): The total payment collected by the exchange from the buyers should be at least the total payment made by the exchange to the sellers.    Individual Rationality (IR): No agent pays more than his bid price or receives less than his ask price.    Incentive Compatibility (IC): The best strategy for agents is to submit bids and asks that reveal their true valuations for the items.
Budget-Balance means that the exchange does not operate at a loss, while Individual Rationality ensures that no agent is made worse off by participating in the exchange. These two conditions must be met by any exchange. Allocative Efficiency is desirable because this is what ensures that the exchange realizes full profit. Incentive Compatibility is a very desirable property because it relieves agents from speculating about the bids and asks of other agents.
Unfortunately the well-known analysis of Myerson and Satterthwaite, Efficient mechanisms for bilateral trading, Journal of Economic Theory 28:265-281, 1983, demonstrates that no exchange can be AE, BB, and IR simultaneously. This result holds irrespectively of IC. Theoretical work so far has focused on trying to design mechanisms where BB, IR, and IC are required and AE is relaxed, such as are described in Myerson and Satterthwaite, Id.; R. McAfee, A dominant strategy double auction, J. of Economic Theory 56:434-450, 1992; and Barbera et al., Strategy-proof exchange, Econometrica 63(1):51-87, 1995. Practical implementations usually ignore IC and AE.
Also known in the art is the so-called Generalized Vickrey Payment Scheme, which is AE, IR and IC, but not BB, such as are described in Varian & MacKie-Mason, Generalized Vickrey auctions, Technical report, University of Michigan (1995); E. H. Clarke, Multipart pricing of public goods, Public Choice 11:17-33, 1971; and T. Groves, Incentives in teams, Econometrica 41:617-631, 1973, the disclosures of all of which are incorporated by reference herein in their entirety. These are based on the so-called Vickrey pricing scheme wherein discount payments are awarded to winning agents at the end of trading, such as is described in W. Vickrey, Counterspeculation, auctions, and competitive sealed tenders, Journal of Finance, 16:8-37, 1961, the disclosures of which are incorporated by reference herein in their entirety.
What is needed is a pricing scheme that is Individual Rational for the agents, Budget Balanced for the market-maker and demonstrates high degrees of Incentive Compatibility and Allocative Efficiency.